如果同时在线人数到达 \(n\),就表示所有人都阅读过;否则,如果总上线人数大于等于 \(n\),则有可能所有人阅读过;否则,不可能所有人阅读过。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| public static void solve() { int n = io.nextInt(), a = io.nextInt(), q = io.nextInt(); String s = io.next(); int cur = a, tot = a; for (int i = 0; i < q && cur < n; i++) { if (s.charAt(i) == '+') { cur++; tot++; } else { cur--; } } if (cur == n) { io.println("YES"); } else if (tot >= n) { io.println("MAYBE"); } else { io.println("NO"); } }
|
对于每个 \(p_{i}=k+1\) 和 \(p_{j}=k\) 并且 \(i<j\),那么就一定要选一次 \(x=k+1\)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| public static void solve() { int n = io.nextInt(); int[] p = new int[n]; for (int i = 0; i < n; i++) { p[i] = io.nextInt() - 1; } int[] map = new int[n]; for (int i = 0; i < n; i++) { map[p[i]] = i; } int ans = 0; for (int i = 1; i < n; i++) { if (map[i] < map[i - 1]) { ans++; } } io.println(ans); }
|
每执行一次操作,就会去除最后一个数,并将 \(MEX\) 添加到序列头部。所以可以通过在数组末尾加上原始数组的 \(MEX\),将操作看成是向左移动循环数组的起始索引。求原始数组的 \(MEX\) 可以使用求和公式。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| public static void solve() { int n = io.nextInt(), k = io.nextInt(); long sum = 0L; int[] a = new int[n + 1]; for (int i = 0; i < n; i++) { a[i] = io.nextInt(); sum += a[i]; } a[n] = (int) ((long) (1 + n) * n / 2 - sum); k = k % (n + 1); for (int i = 0; i < n; i++) { io.print(a[(-k + n + 1 + i) % (n + 1)] + " "); } io.println(); }
|
横放的牌只会对列有影响,竖放的牌只会对行有影响,所以分别处理。按行遍历竖放的牌,每当遇到 \(U\) 就染上和上次相反的颜色,如果该行只包含奇数个 \(U\),就返回 \(-1\)。横放的牌同理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| public static void solve() { int n = io.nextInt(), m = io.nextInt(); char[][] s = new char[n][]; for (int i = 0; i < n; i++) { s[i] = io.next().toCharArray(); } final char[] aux = {'B', 'W'}; for (int i = 0; i < n - 1; i++) { int xor = 0; for (int j = 0; j < m; j++) { if (s[i][j] == 'U') { s[i][j] = aux[xor]; s[i + 1][j] = aux[xor ^ 1]; xor ^= 1; } } if (xor != 0) { io.println(-1); return; } } for (int j = 0; j < m - 1; j++) { int xor = 0; for (int i = 0; i < n; i++) { if (s[i][j] == 'L') { s[i][j] = aux[xor]; s[i][j + 1] = aux[xor ^ 1]; xor ^= 1; } } if (xor != 0) { io.println(-1); return; } } for (int i = 0; i < n; i++) { io.println(new String(s[i])); } }
|
其实思路是知道的,就是不知道怎么写。这个解法看着有点懵,可能其他解法会更好理解一点。注意题目给定 \(a_{i}<b_{i}\)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| public static void solve() { int n = io.nextInt(), m = io.nextInt(), k = io.nextInt(); int[] h = new int[n]; for (int i = 0; i < n; i++) { h[i] = io.nextInt(); } List<Integer>[] g = new List[n]; Arrays.setAll(g, idx -> new ArrayList<>()); for (int i = 0; i < m; i++) { int a = io.nextInt() - 1, b = io.nextInt() - 1; g[a].add(b); } long[] dp = new long[n]; for (int i = n - 1; i >= 0; i--) { for (int j : g[i]) { dp[i] = Math.max(dp[i], dp[j] + (h[j] - h[i] + k) % k); } } long max = 0L; for (int i = 0; i < n; i++) { dp[i] += h[i]; max = Math.max(max, dp[i]); } Integer[] aux = new Integer[n]; for (int i = 0; i < n; i++) { aux[i] = i; } Arrays.sort(aux, (i, j) -> h[i] - h[j]); long ans = Long.MAX_VALUE; for (int i : aux) { ans = Math.min(ans, max - h[i]); max = Math.max(max, dp[i] + k); } io.println(ans); }
|